package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class 优美的排列 {
    int cnt=0;
    public int countArrangement(int n) {
    boolean []visited=new boolean[n+1];
        int deep=0;
        backTracking(deep,n,visited);
        return cnt;
    }

    private void backTracking(int deep, int n,boolean []visited) {
        if(deep==n){
            cnt++;
            return;
        }
        for (int i = 1; i <=n; i++) {
            if(!visited[i]&&((deep+1)%i==0||i%(deep+1)==0)){
                deep++;
                visited[i]=true;
                backTracking(deep,n,visited);
                deep--;
                visited[i]=false;
            }
        }
    }
}